Cos'è torri di?

Torri di Hanoi

Le Torri di Hanoi sono un gioco matematico o un puzzle. Consiste di tre pioli e un certo numero di dischi di diametri diversi, che possono scorrere su qualsiasi piolo. L'obiettivo del gioco è spostare l'intera pila su un altro piolo, rispettando le seguenti regole:

• Solo un disco può essere spostato alla volta.
• Un disco può essere spostato solo se è il disco superiore sul piolo.
• Nessun disco può essere posizionato sopra un disco più piccolo.

Soluzione Ricorsiva

La soluzione più comune al problema delle Torri di Hanoi è un algoritmo ricorsivo. Ecco un riepilogo dell'approccio ricorsivo:

1. Sposta n-1 dischi dal piolo di origine al piolo ausiliario, usando il piolo di destinazione come ausiliario.
2. Sposta l'ultimo disco (il più grande) dal piolo di origine al piolo di destinazione.
3. Sposta gli n-1 dischi dal piolo ausiliario al piolo di destinazione, usando il piolo di origine come ausiliario.

Numero di Mosse

Il numero minimo di mosse necessarie per risolvere le Torri di Hanoi con n dischi è 2^n - 1. Questa crescita esponenziale significa che il problema diventa rapidamente intrattabile all'aumentare del numero di dischi. L'analisi della complessità temporale dell'algoritmo è O(2^n).

Applicazioni

Sebbene sia un puzzle apparentemente semplice, le Torri di Hanoi vengono utilizzate per illustrare:

• Ricorsione
• Algoritmi
• Complessità computazionale

Esempio di Implementazione (Pseudo-codice)

Hanoi(n, origine, destinazione, ausiliario):
  Se n > 0:
    Hanoi(n-1, origine, ausiliario, destinazione)
    Sposta il disco n da origine a destinazione
    Hanoi(n-1, ausiliario, destinazione, origine)